// #include <iostream>
// using namespace std;

// int n;
// const int N=110;
// int arr[N];

// int main() {
//     cin>>n;
//     int sum=0;
//     for(int i=0;i<n;i++){
//         cin>>arr[i];
//         sum+=arr[i];
//     }

//     if(sum%2!=0){
//         cout<<"false"<<endl;
//         return 0;
//     }

//     int target=sum/2;
//     for(int i=0;i<n;i++){
//         int num=arr[i];
//         target-=num;
//         if(target==0) {
//             cout<<"true"<<endl;
//             return 0;
//         }
//         else if(target>0){
//             continue;
//         }
//         else {
//             target+=num;
//         }
//     }
//     cout<<"false"<<endl;
//     return 0;

// }

//01背包问题，用不了贪心

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool dp[510][510*100/2]={0};
    bool partition(vector<int>& nums) {
        int sum=0;
        int n=nums.size();
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sum/2;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum/2];
    }
};